#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 * 207. 课程表
中等
1.5K
相关企业
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。



示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。


提示：

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
 * */

//判断是否有环而已  唉他妈的拓扑排序
//vector<bool> visited;
////存在环返回true
//bool  dfs(int& numCourses,int& startIndex, vector<vector<int>>& prerequisites)
//{
//    //从一点出发能否回到那个点
//    if (visited[startIndex]==true)
//    {
//        return true;
//    }
//
//    for (int i = startIndex; i <prerequisites.size() ; ++i) {
//        visited[startIndex]= true;
//        if (dfs(numCourses,i+1,prerequisites))
//        {
//            return true;
//        }
//        visited[startIndex]=0;
//    }
//
//    return false;
//
//}
//
//
//
//bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//        visited.resize(prerequisites.size(),0);
//
//
//
//
//
//}

//哈哈挺蛋疼的东西
vector<int> inDegree;

//我发现这个numcouses 就是最大课程号比如2 课程是01 后面的数组存储的事那个关系
bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
    inDegree.resize(numCourses);

    unordered_map<int, vector<int>> mp;//一个存储课程 一个存储课程的依赖

    for (int i = 0; i < prerequisites.size(); i++) {
        ++inDegree[prerequisites[i][0]];
        mp[prerequisites[i][1]].push_back(prerequisites[i][0]);//这行原来写反了

    }

    //获取入度为0的存入到队列进行操作
    queue<int> q;//因为这个numcourse 就是所有的课程 直接遍历这个就行
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0)
            q.push(i);
    }
    //记录可以学习的个数

    int count = 0;

    while (!q.empty()) {
        count++;

        int temp = q.front();
        q.pop();

        auto v = mp[temp];

        for (int i = 0; i < v.size(); i++) {
            if ((--inDegree[v[i]]) == 0) {
                q.push(v[i]);
            }

        }

    }


    return count == numCourses;

}